package Algorithm;

public class Feibonaqi {

    static int feibo(int n){

        if (n == 0 ) {
            return 0;
        }

        if (n == 1 || n == 2) {
            return 1;
        }

        return feibo(n-1) + feibo(n - 2);

    }

    static int feibo2(int n){
        if (n == 0 ) {
            return 0;
        }

        if (n == 1 || n == 2) {
            return 1;
        }

        int prev = 1,curr = 1;
        for (int i = 3; i < n; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;

    }


    public static void main(String[] args) {
        System.out.println(feibo2(20));
    }

}
